class Solution:
    class Status:
        def __init__(self, lSum, rSum, mSum, iSum):
            self.lSum = lSum  # 最大左子序列和
            self.rSum = rSum  # 最大右子序列和
            self.mSum = mSum  # 最大子序列和
            self.iSum = iSum  # 区间和

    def pushUp(self, l: 'Status', r: 'Status') -> 'Status':
        iSum = l.iSum + r.iSum
        lSum = max(l.lSum, l.iSum + r.lSum)
        rSum = max(r.rSum, r.iSum + l.rSum)
        mSum = max(l.mSum, r.mSum, l.rSum + r.lSum)
        return self.Status(lSum, rSum, mSum, iSum)

    def get(self, a: list[int], l: int, r: int) -> 'Status':
        if l == r:
            return self.Status(a[l], a[l], a[l], a[l])
        m = (l + r) // 2
        lSub = self.get(a, l, m)
        rSub = self.get(a, m + 1, r)
        return self.pushUp(lSub, rSub)

    def maxSubArray(self, nums: list[int]) -> int:
        return self.get(nums, 0, len(nums) - 1).mSum